package com.smh;

import java.util.Arrays;

/**
 * @author shiminghui
 * @date 2025/3/16 14:59
 * @description: TODO
 */
public class _052_无重叠区间问题 {

    /**
     * 给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
     * <p>
     * 注意 只在一点上接触的区间是 不重叠的。例如 [1, 2] 和 [2, 3] 是不重叠的。
     */
    public int eraseOverlapIntervals(int[][] intervals) {
        // 首先对于区间的结束时间进行升序排序
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
        // 然后遍历区间,如果当前区间的开始时间大于等于前一个区间的结束时间,则当前区间可以加入到结果中
        int count = 1;
        int pre = 0;
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] >= intervals[pre][1]) {
                count++;
                pre = i;
            }
        }
        return intervals.length - count;
    }
}
